﻿// Copyright (c) 2013 fancidev
//
// Permission is hereby granted, free of charge, to any person obtaining a
// copy of this software and associated documentation files (the "Software"),
// to deal in the Software without restriction, including without limitation
// the rights to use, copy, modify, merge, publish, distribute, sublicense,
// and/or sell copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
// THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
// DEALINGS IN THE SOFTWARE.

#if DEBUG
// Define the following to debug the expiry queue.
//#define DEBUG_EXPIRY_QUEUE
#undef DEBUG_EXPIRY_QUEUE
#endif

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Drawing;
using System.Threading;
using Util.Media;

namespace Util.Forms
{
    /// <summary>
    /// Provides animation control for multi-frame images. This class is
    /// optimized for handling a large number of simple, simultaneous 
    /// animations. Because it has no buffering, it is not suitable for
    /// animating a large frame where it takes a lot of time preparing
    /// the frame.
    /// </summary>
    public sealed class AnimationManager : IDisposable
    {
        /// <summary>
        /// Object used to synchronize access to members. This object MUST
        /// be locked when accessing ANY data member of this class except
        /// the FrameExpired event handler.
        /// </summary>
        private object syncObject = new Int32();

        /// <summary>
        /// Mapping from MultiFrameImage to ExpiryInfo. Each image under
        /// control uses exactly one entry in this hash map. If the image
        /// is not scheduled for expiry, the value contains null.
        /// </summary>
        private Dictionary<MultiFrameImage, ExpiryInfo> images
            = new Dictionary<MultiFrameImage, ExpiryInfo>();

        /// <summary>
        /// A queue of frames to watch for expiry. Frames sooner to expire
        /// come first. The expiry time of a frame is expressed in the number
        /// of milliseconds since the Stopwatch started. If this value is 
        /// smaller than or equal to Stopwatch.ElapsedMilliseconds, then the
        /// frame will be marked as expired by the background worker thread.
        /// 
        /// Note that we must NOT use the SortedSet class even though it has
        /// lower time complexity, because if two frames have the same time 
        /// to expiry, they will be considered equal by SortedSet. This is
        /// certainly not what we want.
        /// </summary>
        private LinkedList<ExpiryInfo> expiryQueue = new LinkedList<ExpiryInfo>();

        /// <summary>
        /// Monotonic timer to record a point in time.
        /// </summary>
        private Stopwatch watch = Stopwatch.StartNew();

        /// <summary>
        /// Signal to interrupt the background worker thread from waiting for
        /// the next frame to expire.
        /// </summary>
        private AutoResetEvent signal = new AutoResetEvent(false);

        /// <summary>
        /// Timing resolution in milliseconds. See the Resolution property
        /// for details.
        /// </summary>
        private int resolution = 100;

        /// <summary>
        /// Timing mode of this animation manager.
        /// </summary>
        private AnimationTimingMode timingMode = AnimationTimingMode.Default;

        /// <summary>
        /// Flag indicating whether this object has been disposed.
        /// </summary>
        private bool disposed = false;

        public AnimationManager()
        {
            // Create a background worker thread.
            Thread thread = new Thread(WorkerRoutine);
            thread.IsBackground = true;
            thread.Name = "AnimationManager.WorkerThread";
            thread.Start();
        }

        /// <summary>
        /// Disposes the animation manager and cancels any scheduled 
        /// animation.
        /// </summary>
        public void Dispose()
        {
            lock (syncObject)
            {
                if (disposed)
                    return;

                // Wake up the background worker thread. The worker thread
                // is responsible for disposing the AutoResetEvent.
                signal.Set();

                expiryQueue = null;
                images = null;
                watch = null;
                disposed = true;
            }
        }

        /// <summary>
        /// Gets or sets the timing resolution, in milliseconds, of the 
        /// animation scheduler. This is defined as the minimum time interval
        /// between two successive FrameExpired events.
        /// 
        /// Use this property to balance the timing accuracy and the runtime
        /// overhead of the scheduler. A smaller value results in better 
        /// accuracy but more overhead. The minimum (i.e. best) value allowed
        /// is 1, which allows frames to expire continuously.
        /// 
        /// For a resolution value greater than 1, a frame may be delayed 
        /// than when it should expire. The amount of delay will at most be
        /// the resolution value.
        /// </summary>
        [DefaultValue(100)]
        [Description("Timing resolution of the scheduler in milliseconds.")]
        public int Resolution
        {
            get { return resolution; }
            set
            {
                if (value < 0)
                    throw new ArgumentException("Resolution must be non-negative.");
                resolution = value;
            }
        }

        /// <summary>
        /// Gets or sets the timing mode for frame expiries. This will not
        /// affect frames already scheduled or never scheduled. It only 
        /// take effect when the frame expires and the next frame is scheduled.
        /// </summary>
        public AnimationTimingMode TimingMode
        {
            get { return this.timingMode; }
            set
            {
                if (value != AnimationTimingMode.AfterRendering &&
                    value != AnimationTimingMode.Exact)
                    throw new ArgumentOutOfRangeException("value");
                this.timingMode = value;
            }
        }

        /// <summary>
        /// Background worker routine that monitors frame expiries from 
        /// a dedicated thread.
        /// </summary>
        private void WorkerRoutine()
        {
            while (true)
            {
                int timeToExpiry = 24 * 3600 * 1000; // in milliseconds
                ExpiryInfo expiredItem = null;

                // Get the first expired frame if one exists, or leave
                // timeToExpiry with a positive value to indicate the
                // number of milliseconds to wait.
                lock (syncObject)
                {
                    if (disposed)
                    {
                        signal.Dispose();
                        return;
                    }

                    if (expiryQueue.Count > 0)
                    {
                        timeToExpiry = (int)Math.Min(
                            expiryQueue.First.Value.ExpiryTime - watch.ElapsedMilliseconds,
                            Int32.MaxValue);
                        if (timeToExpiry <= 0) // expired
                        {
                            expiredItem = expiryQueue.First.Value;
                            expiryQueue.RemoveFirst();
                            expiredItem.Expire();
#if DEBUG_EXPIRY_QUEUE
                            System.Diagnostics.Debug.WriteLine(string.Format(
                                "[{0:HH:mm:ss.ff}] ExpiryQueue: Removed {1}",
                                DateTime.Now, expiredItem.Image.Name));
#endif
                        }
                    }
                }

                if (expiredItem != null)
                {
                    // Raise FrameExpired event.
                    if (FrameExpired != null)
                    {
                        FrameExpired(this, new FrameExpiredEventArgs(expiredItem.Image));
                    }
                }
                else
                {
                    // Either there are no frames in the queue or the first
                    // frame is yet to expire. Wait for it to expire while
                    // observing the signal from the main thread. Wait at
                    // least Resolution milliseconds to reduce overhead.
#if DEBUG_EXPIRY_QUEUE
                    timeToExpiry = Math.Max(timeToExpiry, 500);
#else
                    timeToExpiry = Math.Max(timeToExpiry, resolution);
#endif
                    signal.WaitOne(timeToExpiry);
                }
            }
        }

        private ExpiryInfo ScheduleCurrentFrameForExpiry(
            MultiFrameImage image, long startTime, long minimumDelay)
        {
#if DEBUG
            // Sanity check.
            //if (expiryQueue.Contains(info))
            //    throw new InvalidOperationException("Internal error: the item is already in the expiry queue.");
#endif

            // Schedule this item for expiry.
            long delay = (long)image.FrameDelay.TotalMilliseconds;
            delay = Math.Max(delay, minimumDelay);
            long expiryTime = startTime + delay;
            ExpiryInfo info = new ExpiryInfo(image, expiryTime);

            // TODO: The spinner seems to spin slower than it
            // should be. This means we should base the expiry
            // time on CreateTime, rather than on RenderTime.
            // This will make the video play at the requested
            // speed.

            // Insert the item into the proper position in the expiry queue,
            // with items closer to expiry placed first.
            var node = expiryQueue.First;
            while (node != null)
            {
                if (node.Value.ExpiryTime > info.ExpiryTime)
                    break;
                node = node.Next;
            }
            if (node == null)
                expiryQueue.AddLast(info);
            else
                expiryQueue.AddBefore(node, info);

            signal.Set();
            return info;
        }

        /// <summary>
        /// Adds a multi-frame image to the animation manager.
        /// 
        /// If TimingMode is AfterRendering, the timing does not start until
        /// the first call to GetCurrentFrame() with 'rendering' set to true.
        /// If TimingMode is Exact, the timing starts immediately.
        /// 
        /// If the image has been added to the animation manager previously,
        /// this method does nothing.
        /// </summary>
        /// <param name="image">The image to add to animation control.</param>
        public void Add(MultiFrameImage image)
        {
            if (image == null)
                throw new ArgumentNullException("image");

            lock (syncObject)
            {
                if (disposed)
                    throw new ObjectDisposedException("AnimationManager");

                // Do nothing if the image is already under management.
                if (images.ContainsKey(image))
                    return;

                // Create an ExpiryInfo entry for this image.
                if (timingMode == AnimationTimingMode.Exact)
                {
                    long now = watch.ElapsedMilliseconds;
                    ExpiryInfo info = ScheduleCurrentFrameForExpiry(image, now, 0);
                    images.Add(image, info);
                }
                else if (timingMode == AnimationTimingMode.AfterRendering)
                {
                    // Add dummy entry because we don't schedule it now.
                    images.Add(image, null);
                }
                else
                {
                    throw new NotSupportedException("TimingMode is not supported.");
                }
            }
        }

        /// <summary>
        /// Gets the current frame of the multi-frame image, and optionally
        /// notifies the scheduler to schedule the next frame for expiry if
        /// not already scheduled.
        /// 
        /// This method should be used to access the active frame in an image
        /// instead of accessing its Frame property directly for two reasons:
        /// 
        /// 1, This method can notify the scheduler that the current frame is
        ///    rendered, so that the scheduler can schedule the current frame
        ///    for expiry if not already done so.
        /// 2, It avoids potential synchronization problems as the image may
        ///    be accessed from a background thread within the scheduler.
        /// </summary>
        /// <param name="image">The image whose frame to get. This image must
        /// have previously been added to this scheduler via Add().</param>
        /// <param name="rendering">If set to true, instructs the scheduler
        /// to schedule for the next frame of this image.</param>
        /// <returns></returns>
        /// <remarks>
        public Image GetCurrentFrame(MultiFrameImage image, bool rendering)
        {
            // If the user is not rendering, it's none of our business.
            if (!rendering)
                return image.Frame;

            long now = watch.ElapsedMilliseconds;
            lock (syncObject)
            {
                if (disposed)
                    throw new ObjectDisposedException("AnimationManager");

                // Get the current expiry info entry of this image. This value
                // may be null if the timing mode was AfterRendering when the
                // image was added and the image was never rendered.
                ExpiryInfo info;
                if (!images.TryGetValue(image, out info))
                {
                    throw new ArgumentException("The requested image is not " +
                        "under the control of this animation manager.");
                }

                // If the image has never been scheduled, shedule it now.
                // This can only happen if TimingMode was AfterRender when
                // the image was added and this is the first time the image
                // is rendered.
                if (info == null)
                {
                    images[image] = ScheduleCurrentFrameForExpiry(image, now, 0);
                    return image.Frame;
                }

                // If the current frame has not expired, just return it.
                if (!info.Expired)
                    return image.Frame;

                // Advance (or loop) the frame until the frame's expiry time
                // is later than 'now'.

                // TODO: The current method is very slow when a lot of frames
                // are lost. Clearly we need to optimize away the loop if we
                // want to make Exact mode usable.
                long startTime = (timingMode == AnimationTimingMode.Exact) ?
                                 info.ExpiryTime : now;
                while (true)
                {
                    image.AdvanceFrame(true);
                    long delay =  (long)image.FrameDelay.TotalMilliseconds;
                    // Put a lower limit on the frame delay. Otherwise if we get
                    // a delay of zero, we'll loop infinitely.
                    
                    // Make a special case if the frame delay is zero. That means
                    // the multi-frame image is actually unrelated frames, which
                    // are not supposed to be put in animation.

                    //if (delay == 0)
                    //    delay = 100;
                    delay = Math.Max(delay, 100);
                    if (startTime + delay <= now)
                        startTime += delay;
                    else
                        break;
                }

                // Schedule the current frame for expiry, and update the 
                // expiry entry in the dictionary.
                images[image] = ScheduleCurrentFrameForExpiry(image, startTime, 100);
                return image.Frame;
            }
        }

        /// <summary>
        /// Occurs when the current frame of one of the images has expired.
        /// A frame expires when both of the following conditions are met:
        /// 1 - It has been rendered at least once via the GetCurrentFrame()
        ///     call, and
        /// 2 - FrameDelay amount of time has passed since the first time
        ///     this frame was rendered.
        /// This event is raised exactly once each time a frame expires.
        /// </summary>
        public event EventHandler<FrameExpiredEventArgs> FrameExpired;

        enum AnimationStatus
        {
            Pending = 0,
            Scheduled = 1,
            Expired = 2,
        }

        // TODO: add separate animation info entry for each frame.
        class ExpiryInfo
        {
            /// <summary>
            /// Gets the image whose frame is being monitored for expiry.
            /// </summary>
            public MultiFrameImage Image { get; private set; }

            /// <summary>
            /// Get the time the frame being monitored is scheduled to expire,
            /// expressed in the number of milliseconds since the Stopwatch 
            /// started.
            /// </summary>
            public long ExpiryTime { get; private set; }

            /// <summary>
            /// Gets a flag indicating whether the frame being monitored has
            /// expired.
            /// </summary>
            public bool Expired { get; private set; }

            public ExpiryInfo(MultiFrameImage image, long expiryTime)
            {
                this.Image = image;
                this.ExpiryTime = expiryTime;
                this.Expired = false;
            }

            public void Expire()
            {
                if (this.Expired)
                    throw new InvalidOperationException("Cannot expire twice.");
                this.Expired = true;
            }
        }
    }

    public enum AnimationTimingMode
    {
        /// <summary>
        /// The default timing mode.
        /// </summary>
        Default = AfterRendering,
        //Default = Exact,

        /// <summary>
        /// Starts timing after the frame is rendered. When 'delay' amount of
        /// time has passed after the frame is first rendered, the frame is 
        /// expired and the FrameExpired event is raised. The user notifies 
        /// the animation manager that a frame has been rendered by calling 
        /// the GetCurrentFrame() with 'rendering' set to true.
        /// </summary>
        /// <remarks>
        /// In this timing mode, no frames will be lost, and images that 
        /// never got rendered (such as those invisible) will not raise
        /// FrameExpired events, which saves computation resources. However,
        /// this mode tends to play an animation slow because of the delay
        /// from the old frame is expired till the new frame gets rendered.
        /// 
        /// The timeline of events in a typical usage scenario where
        /// TimingMode is set to AfterRendering is illustrated below:
        /// 
        /// T0: Frame expires.
        /// T1: Animation manager raises FrameExpired event and optionally
        ///     marshals the event call to the UI thread.
        /// T2: The UI thread handles the FrameExpired event. It invalidates
        ///     and optionally updates the control.
        /// T3: The control handles OnPaint(), and acknowledge the expiry by
        ///     calling AnimationManager.GetCurrentFrame(true). In this call,
        ///     the animation manager loads the next frame, schedules the new
        ///     frame for expiry, and returns the new frame.
        /// </remarks>
        AfterRendering = 0,

        /// <summary>
        /// Starts timing after the previous frame expires. When 'delay'
        /// amount of time has passed since the previous frame expires, the
        /// new frame is expired and the FrameExpired event is raised.
        /// 
        /// However, if an expired frame is not rendered, later frame expiries
        /// do not raise the FrameExpired event to prevent the user from
        /// receiving too many events from invisible items.
        /// 
        /// In this timing mode, the frames are played at their designed rate,
        /// and frames may be lost if not rendered in time. If the latency 
        /// between a frame is expired and the next frame is rendered is
        /// roughly similar across all frames, then the animation will look
        /// in pace with the design rate.
        /// 
        /// The timing starts as soon as the image is added to the manager.
        /// </summary>
        Exact = 1,
    }

    public class FrameExpiredEventArgs : EventArgs
    {
        private MultiFrameImage image;

        public FrameExpiredEventArgs(MultiFrameImage image)
        {
            if (image == null)
                throw new ArgumentNullException("image");
            this.image = image;
        }

        /// <summary>
        /// Gets the multi-frame image whose frame has expired. Note that the
        /// expired frame may not be the current frame. Consider for example
        /// the following sequence of events:
        ///
        /// [00:00:00] Thread A calls Add(image).
        /// [00:00:01] Thread A calls GetCurrentFrame(image). The current 
        ///            frame is set to 0, and scheduling begins.
        /// [00:00:02] Thread B, the scheduler thread, finds the frame expired
        ///            and raises the FrameExpired event, which invokes the
        ///            event handler by posting a message to Thread A.
        /// [00:00:03] Thread A has a lot of messages in the message queue,
        ///            and before it can process the FrameExpired event, it 
        ///            calls GetCurrentFrame(image), which updates the frame 
        ///            index to 1.
        /// [00:00:04] Thread A finally gets to process the FrameExpired
        ///            event posted for frame 0. To handle it property, it 
        ///            must not think that frame 1 has expired.
        /// 
        /// A rule of thumb to avoid concurrency problems in this case is to
        /// only do safe things in the event handler, such as invalidating
        /// the control.
        /// </summary>
        public MultiFrameImage Image { get { return image; } }
    }
}
